package dp;

/**
 * @author tmh
 * @date 2024/9/17 15:48
 * @description
 */
public class T718最长重复子数组 {
    //以i-1为结尾的nums1和以j-1结尾的nums2的最长重复子数组的长度是dp[i][j]
    //PS：这里i-1结尾的数要和j-1结尾的数相同才可以计算重复子数组的长度
    //假如i-1的值是1，j-1的值是7，那么以他们两个结尾的最长重复子数组的长度就是0；因为两个值不同
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //定义一个result来保存最后的结果，因为最后的dp[m][n]不一定是最大
        int result = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (result < dp[i][j]) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
}
